1. Field of the Invention
The present invention relates to logic circuits, and more particularly to implementations of high fan-in complex logic functions in a dynamic logic circuit.
2. Description of the Related Art
Dynamic circuits are frequently used to implement logic functions in present day pipelined systems because of speed demands. FIG. 1 is a schematic diagram of an AND gate 100 representing an AND logic function and an exemplary dynamic circuit 102 for implementing the AND gate 100. The dynamic circuit 102 and the AND gate 100 each are shown having xe2x80x9cNxe2x80x9d inputs, individually shown as D1, D2, . . . , DN, and a single output referred to as xe2x80x9cQxe2x80x9d. The dynamic circuit 102 includes a P-channel header device P0 an N-channel footer device N0, a logic function for evaluation implemented by a logic circuit 104, an output buffer or inverter/driver U1, and a storage or keeper circuit 106. In the embodiment shown, the keeper circuit 106 is implemented with inverter devices U2 and U3, in which the output of U2 is coupled to the input of U3 and vice-versa.
The dynamic circuit 102 establishes the Q signal at the output of the inverter/driver U1 on a rising edge of an associated clock signal xe2x80x9cCLKxe2x80x9d. The dynamic nature of a dynamic logic circuit is controlled by the CLK signal in which the circuit is in a set-up or pre-charged state while CLK is negated low and in an evaluation state when CLK is asserted high. The CLK signal is provided to respective gates of the header device P0 and the footer device N0. The header device P0 has a source coupled to a source voltage xe2x80x9cVDDxe2x80x9d and a drain coupled to an evaluation node referred to as xe2x80x9cHIxe2x80x9d. It is noted that a node and its corresponding signal are referred to herein by the same name, e.g., node HI carries the HI signal. The footer device N0 has a source coupled to a common reference voltage xe2x80x9cGNDxe2x80x9d and a drain coupled to a reference node referred to as xe2x80x9cLOxe2x80x9d. The logic circuit 104 is coupled between the HI and LO nodes. In the embodiment shown, the logic circuit 104 is implemented in N-channel logic, or xe2x80x9cN-logicxe2x80x9d, using a number xe2x80x9cNxe2x80x9d of N-channel devices N1-NN coupled in series between the HI and LO nodes. In particular, a first N-channel device N1 has its drain coupled to HI and its source coupled to the drain of the next N-channel device N2, and so on down to a last N-channel device NN having its source coupled to LO. Each of the N inputs D1-DN is provided to a respective one of the N-channel devices N1-NN. The HI node is further coupled to the inputs of the inverter devices U1 and U2 and to the output of the inverter device U3.
In operation, while the CLK signal is low, the HI node is pre-charged to a logic high level by the header device P0, the Q signal is pulled low via the inverter/driver U1 and the input signals D1-DN setup for evaluation of the logic function. When the CLK signal goes high, based on the state of the inputs D1-DN, the logic function of the logic circuit 104 either evaluates or xe2x80x9cfailsxe2x80x9d to evaluate. If the logic circuit 104 evaluates, in which all of the input signals D1-DN are asserted high turning on all of the N-channel devices N1-NN, the logic circuit 104 drives the HI node to a logic low level via the activated footer device N0 and the Q output signal is driven to a logic high level. Once the HI node is driven low, it stays low until the CLK signal is driven low again. If the logic circuit 104 fails to evaluate, the keeper circuit 106 maintains the HI node at a high logic level, so that the Q signal remains low. Hence, the Q signal is low when the CLK signal is low, and the Q signal can be driven high by the logic circuit 104 while the CLK signal is high if the logic function is TRUE.
The logic function implemented by the logic circuit 104 is a multiple-input AND function. To evaluate, all of the inputs D1-DN must be at a logic high level while the CLK signal is high. AND logic functions are typically implemented in N-logic by connecting N-channel devices in series as shown within the logic circuit 104. Such series or xe2x80x9cstackxe2x80x9d connections of N-channel devices causes problems in a dynamic circuit for at least two reasons. First, the length of the evaluation path between the HI and LO nodes is a function the number of devices in the evaluation path of the logic circuit which is, in turn, a function of the fan-in (i.e., the number of inputs to be ANDed together). Long evaluation paths required to evaluate a relatively large number of input signals requires a longer time to evaluate, thus slowing down the overall circuit. Second, because N-channel devices are employed to implement the evaluation function, devices higher in the stack are subject to device body effects. Device body effects cause the device thresholds to change due to stacking, thus providing the potential for instability of the circuit.
To address the problems associated with the length of the evaluation path, logic designers usually limit the size of each stack to no more than about four levels. In general, evaluation paths with two levels is a desirable configuration. The solution of limiting the evaluation path may be accomplished by either implementing the inverse function using OR terms or decomposing high fan-in AND functions into a staged series of low fan-in AND functions.
Implementing the inverse of an AND function involves converting the series AND path to a parallel OR path with parallel OR terms. The solution of inverting to the OR logic function suffices for simple functions in which an inverted output is acceptable. The inversion solution is unworkable under complex logic conditions, however, since converting AND terms to OR terms in a first stage of a logic operation necessitates that OR terms in a following stage be converted to AND terms. Consequently, inversion merely relegates the N-stack problem to the following logic stage.
FIG. 2 is a schematic diagram of a 16-input AND gate 200 and an exemplary logic circuit 202 for implementing the AND gate 200 illustrating a conventional decomposition solution. The AND gate 200 has 16 input signals, individually shown as A1-A16, and an output signal Q, and is considered a high fan-in AND function. The single AND gate 200 is implemented by a series of four low fan-in stages 204, 206, 208 and 210, each stage including one or more 2-input AND gates. In particular, the first stage 204 includes eight AND gates, each receiving a respective pair of the input signals A1-A16. The second stage 206 includes four AND gates, each having a pair of inputs coupled to respective outputs of pairs of AND gates of the first stage 204. The third stage 208 includes two AND gates, each having a pair of inputs coupled to respective outputs of pairs of AND gates of the second stage 206. The fourth and final stage 210 includes a single AND gate having a pair of inputs coupled to respective outputs of the two AND gates of the third stage 208.
It is noted that each AND function of the logic circuit 202 has only two inputs so that the respective evaluation paths are decomposed to the desirable configuration with low fan-in. Decomposing a high fan-in AND function into staged low fan-in AND operations is undesirable, nevertheless, because each additional series-coupled stage of the decomposed function adds delay to the overall circuit. The number of AND gates may be decreased by increasing the fan-in per AND gate, such as down to only five 4-input AND gates, each with the maximum number of recommended fan-ins of four. This latter solution still suffers from delay, however, since each AND function has a relatively large fan-in and two stages are still required.
A complementary input dynamic logic circuit for evaluating a complex logic function according to an embodiment of the present invention includes complementary input dynamic logic circuits, P-channel devices, an inverter/driver for providing an inverted clock signal, and N-channel pass devices. Each complementary input dynamic logic circuit determines a complementary AND function for a corresponding one of multiple sets of AND terms and indicates the complementary AND function via a corresponding one of multiple preliminary evaluation nodes. The P-channel devices are coupled in series between a source voltage and an output evaluation node. Each series-coupled P-channel device has a gate coupled to a corresponding preliminary evaluation node. The N-channel pass devices are coupled in parallel between the output evaluation node and the inverter/driver. Each N-channel pass device has a gate coupled to a corresponding preliminary evaluation node. An output driver or inverter/driver may be provided to buffer and/or invert the output evaluation node and provide a logic function result.
A complementary input dynamic logic circuit according to another embodiment of the present invention includes multiple complementary N-logic AND circuits, pairs of header and footer devices, a P-logic circuit, and an N-logic pass circuit. Each complementary N-logic AND circuit is coupled to a corresponding one of multiple preliminary evaluation nodes and includes at least one input for receiving a corresponding set of AND terms. Each pair of header and footer devices is responsive to a clock signal to pre-charge a preliminary evaluation node and to enable a corresponding complementary N-logic AND circuit to evaluate. The P-logic circuit is coupled to the preliminary evaluation nodes and to an output evaluation node to pull the output evaluation node high if each of the complementary N-logic AND circuits evaluates. The N-logic pass circuit is coupled between the output evaluation node and the preliminary evaluation nodes and pulls the output evaluation node low if any one of the N-logic AND circuits fails to evaluate.
A method of evaluating a complex dynamic logic function according to an embodiment of the present invention includes simultaneously evaluating sets of AND terms using corresponding complementary AND logic circuits, controlling corresponding preliminary evaluation nodes indicative of respective AND logic evaluations, monitoring each of the preliminary evaluation nodes via P-logic which pulls an output evaluation node high if each of the complementary AND logic circuits evaluate, and monitoring each of the preliminary evaluation nodes via N-logic, which pulls the output evaluation node low if any of the complementary AND logic circuits fail to evaluate.